package leetcode;

import java.util.ArrayList;
import java.util.HashMap;

public class LetterCombination {
	private static ArrayList<String> result2 = new ArrayList<String>();
	private static StringBuilder builder = new StringBuilder();
	private static HashMap<Character, char[]> map = new HashMap<Character, char[]>();

	public ArrayList<String> letterCombinations(String digits) {
		map.put('2', "abc".toCharArray());
		map.put('3', "def".toCharArray());
		map.put('4', "ghi".toCharArray());
		map.put('5', "jkl".toCharArray());
		map.put('6', "mno".toCharArray());
		map.put('7', "pqrs".toCharArray());
		map.put('8', "tuv".toCharArray());
		map.put('9', "wxyz".toCharArray());
		if (digits == null || digits.length() <= 0) {
			result2.add(new String());
			return result2;
		}
		char[] numbers = digits.toCharArray();
		backtrackingOfLetter(numbers, map.get(numbers[0]), numbers.length, 0);
		return result2;
	}

	public void backtrackingOfLetter(char[] number, char[] array, int remain,
			int start) {
		if (remain == 0) {
			result2.add(new String(builder));
			// System.out.println(" builder value : " +builder.toString());
		} else {
			int i;
			for (i = start; i < array.length; i++) {
				// System.out.println("char: " + array[i] + " i:" + i);
				builder.append(array[i]);
				int length = number.length - remain + 1;
				backtrackingOfLetter(number, length >= number.length ? null
						: map.get(number[length]), remain - 1, 0); // 寻找下一个
				builder.deleteCharAt(builder.length() - 1);
			}
		}
	}
}
